/*
 * @lc app=leetcode.cn id=994 lang=cpp
 *
 * [994] 腐烂的橘子
 */

// @lc code=start
class Solution
{
public:
    struct Cell
    {
        int i, j, step;
        Cell(int i, int j, int step) : i(i), j(j), step(step) {}
    };

    int orangesRotting(vector<vector<int>> &grid)
    {
        int m = grid.size(), n = grid[0].size(), fresh = 0, ans = 0;
        queue<Cell> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 2)
                    q.push(Cell(i, j, 0));
                else if (grid[i][j] == 1)
                    fresh++;
            }
        }
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!q.empty())
        {
            Cell curr = q.front();
            q.pop();
            ans = curr.step;
            for (auto [di, dj] : dirs)
            {
                int i = curr.i + di, j = curr.j + dj;
                if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 1)
                {
                    continue;
                }
                grid[i][j] = 2;
                fresh--;
                q.push(Cell(i, j, curr.step + 1));
            }
        }

        return fresh == 0 ? ans : -1;
    }
};
// @lc code=end
